package com.second.app.huaweiod;

public class PaixuDemo {

    public static void main(String[] args) {

        // 输入目标元素，在一个有序数组里面找出，找到返回索引，找不到返回-1；

//        int[] arr2 = {
//                1, 2, 3, 6, 9, 100, 200, 201
//        };
//
//        System.out.println("=====" + binarySearch(arr2, 9));
//
//
//        int[] arr = {10, 5, 8, 7, 20, 6, 3};
//        bubbleSort(arr);
//        System.out.println("-------冒泡排序-------结果如下");
//        for (int x = 0; x < arr.length; x++) {
//            System.out.println("第" + (x + 1) + "个元素" + arr[x]);
//        }
//
//        int[] arr1 = {10, 5, 8, 7, 20, 6, 3, 2, 1000, 88};
//        chooseSort(arr1);
//        System.out.println("-------选择排序-------结果如下");
//        for (int x = 0; x < arr1.length; x++) {
//            System.out.println("第" + (x + 1) + "个元素" + arr1[x]);
//        }


        int[] arr3 = {10, 5, 8, 7, 20, 6, 3, 2, 1000, 88};
        quickSort(arr3, 0, arr3.length - 1);

        for (int num : arr3) {
            System.out.println(num + " ");
        }
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return; // 递归终止条件

        int pivot = arr[left]; // 选择第一个元素作为基准
        int i = left, j = right;

        while (i < j) {
            // 从右往左找小于 pivot 的元素
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            arr[i] = arr[j];
            // 从左往右找大于 pivot 的元素
            while (i < j && arr[i] <= pivot){
                i++;
            }
            arr[j] = arr[i];
        }

        arr[i] = pivot; // 放置基准元素

        // 递归排序左右两部分
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }

    public static Integer binarySearch(int[] arr, int target) {

        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }


    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void chooseSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }


        }
    }
}
